class Solution(object):
    def numPrimeArrangements(self, n):
        """
        :type n: int
        :rtype: int
        """
        P = [1 for _ in range(n - 1)]
        primes = []
        for i in range(n - 1):
            if P[i]:
                primes.append(i + 2)
            for num in primes:
                if num * (i + 2) <= n:
                    P[num * (i + 2) - 2] = 0
                    if (i + 2) % num == 0:
                        break
                else:
                    break
        zhishu = len(primes)
        heshu = n - len(primes)
        base = 1
        for i in range(1, zhishu + 1):
            base = base * i % (10**9 + 7)
        for i in range(1, heshu + 1):
            base = base * i % (10**9 + 7)
        return base


data = Solution()
n = 100
print(data.numPrimeArrangements(n))
